#!/usr/bin/env python
# -*- coding:utf-8 -*-
# @Author  : 邢建辉
# @Email   : xjh_0125@sina.com
# @Time    : 2021/12/31 14:04
# @Software: PyCharm
# @File    : l1675_minimum_deviation.py
from typing import List

import heapq
import bisect


class Solution:
    def minimumDeviation_tmp(self, nums: List[int]) -> int:
        def getDeviation(odds, evens):
            if len(odds) == 0:
                return evens[-1] - evens[0]
            if len(evens) == 0:
                return odds[-1] - odds[0]
            res = max(odds[-1], evens[-1]) - min(odds[0], evens[0])
            return res

        def insertToArray(li, num):
            try:
                if len(li) > 0:
                    idx = bisect.bisect_left(li, num)
                    if idx == len(li):
                        li.append(num)
                    elif li[idx] != num:
                        li.insert(idx, num)
                else:
                    li.append(num)
            except:
                print(li, num)

        nums = sorted(list(set(nums)))
        odds = []
        evens = []
        max_res = nums[-1] + 1
        for num in nums:
            if num % 2 == 0:
                evens.append(num)
            else:
                odds.append(num)
        if len(odds) == 0:
            tmp = evens.pop()
            while tmp % 2 == 0:
                tmp /= 2
            insertToArray(odds, tmp)
        if len(evens) == 0:
            insertToArray(evens, odds.pop(0) * 2)
        while len(evens) > 0 or len(odds) > 0:
            cur_res = getDeviation(evens, odds)
            if cur_res > max_res:
                return int(max_res)
            elif cur_res < max_res:
                max_res = cur_res
                switch_odd = False
                switch_even = False
                if len(odds) > 0 and len(evens) > 0:
                    cur_max = max(odds[-1], evens[-1])
                    cur_min = min(odds[0], evens[0])
                    if cur_min % 2 == 0 and cur_max % 2 == 1:
                        break
                    elif cur_max % 2 == 0 and cur_min % 2 == 1:
                        tmp_even = evens[-2] if len(evens) > 1 else evens[-1]
                        tmp_odd = odds[1] if len(odds) > 1 else evens[0]
                        switch_odd = max(cur_max / 2, odds[-1], tmp_even) - min(cur_min, cur_max / 2) > \
                                     max(cur_max, cur_min * 2) - min(cur_min * 2, tmp_odd, evens[0])
                        switch_even = not switch_odd

                    elif cur_min % 2 == 1:
                        switch_odd = True
                    else:
                        switch_even = True
                if len(odds) > 0 and switch_odd:
                    if len(evens) == 0 or odds[0] < evens[0]:
                        tmp_odd = odds.pop(0)
                        insertToArray(evens, tmp_odd * 2)
                if len(evens) > 0 and switch_even:
                    tmp = 0
                    if len(odds) > 0:
                        tmp = odds[-1]
                    if tmp < evens[-1]:
                        tmp_even = evens.pop()
                        tmp_even /= 2
                        if tmp_even % 2 == 0:
                            insertToArray(evens, tmp_even)
                        else:
                            insertToArray(odds, tmp_even)
            else:
                break
        if len(evens) == 0:
            return int(min(odds[-1] - odds[0], max_res))
        elif len(odds) == 0:
            return int(min(evens[-1] - evens[0], max_res))
        else:
            return int(max_res)

    def minimumDeviation_1(self, nums: List[int]) -> int:
        def insertToArray(li, num):
            try:
                if len(li) > 0:
                    idx = bisect.bisect_left(li, num)
                    if idx == len(li):
                        li.append(num)
                    elif li[idx] != num:
                        li.insert(idx, num)
                else:
                    li.append(num)
            except:
                print(li, num)

        s = set()
        for num in nums:
            s.add(num if num % 2 == 0 else num * 2)
        li = sorted(s)
        res = li[-1] - li[0]
        while res > 0 and li[-1] % 2 == 0:
            tmp = li.pop()
            insertToArray(li, tmp / 2)
            res = min(res, li[-1] - li[0])
        return int(res)

    def minimumDeviation(self, nums: List[int]) -> int:
        s = set()
        for num in nums:
            s.add(num if num % 2 == 0 else num * 2)
        li = [-i for i in s]
        heapq.heapify(li)
        res = heapq.nsmallest(1, li)[0] * -1 - heapq.nlargest(1, li)[0] * -1
        while res > 0 and heapq.nsmallest(1, li)[0] % 2 == 0:
            tmp = heapq.heappop(li)
            heapq.heappush(li, tmp / 2)
            res = min(res, heapq.nsmallest(1, li)[0] * -1 - heapq.nlargest(1, li)[0] * -1)
        return int(res)


if __name__ == '__main__':
    s = Solution()
    nums = [1, 2, 6, 8]

    nums = [2, 10, 8, 16]
    nums = [100092626, 100190707, 100216855, 100587965, 100838796, 101258267, 101600108, 101977678, 102072773,
            102127258, 102263907, 102484169, 102498490, 102505057, 103114996, 103162165, 103516387, 103569746,
            103599601, 103701602, 104014213, 105129765, 105243015, 105245785, 105493962, 105628049, 105888611,
            106113788, 106983428, 107100346, 107901250, 108277946, 108451832, 108470642, 108640913, 108986309,
            109366482, 109423556, 109853721, 110023818, 111055030, 111227228, 111611931, 112171085, 112237013,
            113282879, 113431868, 113507815, 114061225, 114131106, 114476348, 114642866, 114722931, 115017904,
            115345543, 115461652, 115718199, 115753487, 115915326, 116045000, 116121994, 116145251, 117310304,
            117471904, 117558856, 117651449, 117768984, 118407455, 118665099, 119184450, 119749615, 119758139,
            120013972, 120065496, 120472984, 121342141, 121580658, 122308978, 123456024, 123588933, 124266013,
            124355592, 124394249, 124536617, 124778611, 124972645, 125527818, 125782453, 125841090, 127024993,
            127347508, 127439843, 127509228, 127662367, 127663274, 127805067, 128106398, 128452102, 128959020,
            128964739, 129079222, 129187299, 129959078, 130131460, 130394674, 130710611, 130956004, 132326257,
            132487910, 132630801, 133032247, 133909934, 134565576, 135266151, 135798617, 135845950, 135853494,
            136108423, 136108503, 136191103, 136718954, 136872491, 137044502, 137400257, 137725843, 138042671,
            138164718, 138488715, 138765154, 138858670, 138882615, 139403775, 139405172, 139405555, 139492998,
            139502287, 139608067, 139697220, 139727086, 140093586, 140254982, 140563651, 140572589, 140579776,
            140631914, 140651548, 141158921, 141314732, 141567001, 141871659, 142054441, 142084051, 142091904,
            142144983, 142241150, 142432287, 142687756, 143305183, 143353678, 143562844, 143836292, 143972099,
            144583353, 144881521, 145565683, 145984705, 146122849, 146619923, 146780066, 147130259, 147699018,
            147725900, 148148621, 148201456, 148387216, 149364536, 149432483, 149852668, 149859250, 150336410,
            150545120, 150810789, 150872767, 152560087, 152949311, 153149280, 153587163, 153948939, 154488151,
            154925409, 155340595, 155342972, 155915678, 155970321, 156257215, 156427959, 156505003, 157330716,
            157552714, 157811076, 158050009, 158224131, 158258043, 158492279, 159321118, 159632836, 160145942,
            160653221, 160770301, 160897452, 161630895, 161774593, 161910843, 161927809, 162317887, 162645972,
            162721361, 163176045, 163189619, 163267954, 164259991, 164457368, 164716217, 164739980, 165113533,
            165365010, 165425337, 165486776, 165570519, 165621480, 165834418, 166224862, 166356073, 166392273,
            166492711, 166594704, 167154441, 167485119, 167771287, 168628878, 168756945, 168807287, 169538709,
            169993800, 170141845, 170588551, 170848534, 170925551, 171044990, 171152787, 171156531, 171322947,
            171503536, 171861205, 172900728, 172915905, 173477124, 173602535, 173657901, 173770396, 173895760,
            174511822, 174858873, 175430770, 175774728, 176016355, 176020777, 176058211, 176113588, 176351775,
            176380601, 176811279, 177018029, 177159816, 177230274, 177284541, 178418731, 178518694, 178875891,
            179515445, 179566227, 179583881, 180008386, 180198468, 180400034, 180664549, 180827841, 181140323,
            181173340, 182202999, 182229265, 182464664, 182874278, 183467485, 183508477, 184521526, 184930698,
            185321487, 186169756, 186233414, 186326112, 186435019, 186652919, 186679088, 186774576, 186941874,
            187121403, 187461591, 187813699, 187931161, 187953441, 188489301, 188496780, 188650252, 188843428,
            189004451, 189463437, 190480953, 191279346, 191502543, 192320235, 192371264, 192791912, 192825874,
            192910027, 192978346, 193146386, 193558089, 193569603, 194267446, 194312999, 195316256, 195643978,
            195738467, 195801072, 196724440, 197087073, 197119385, 197553755, 197600861, 198131866, 198133057,
            198163856, 198186644, 198344152, 199320902, 199332316, 199403460, 199607036, 199766954,
            199913646]  # 98683701
    # nums = [331, 357, 399, 502, 596, 648, 649, 693, 698, 908]  # 315
    # nums = [100092626, 100190707, 198163856, 198186644, 198344152, 199320902, 199332316, 199403460, 199607036,199766954, 199913646]
    print(s.minimumDeviation(nums))
    # print(1)
